1. Field of the Invention
This invention relates to database management systems and in particular to a system and method for mixed-mode concurrency control of access to shared objects.
2. Description of the Related Art
The background of the invention is described in connection with database management systems as an example.
Without concurrency control a database with shared objects may become corrupted by transactions which operate in parallel. Consider a program which reads an object, increments its value, and stores the resulting value back into the object. If this program is executed simultaneously in two transactions, there is a potential for having an incorrect result stored in the object. Both transactions may read the same value, the value originally stored in the object. If both objects in parallel increment the value and sequentially store their respective results, the final value stored in the object only reflects one increment. This could have disastrous results. For example, in an airline reservation system, if the program counts the number of seats sold to a flight, such a transaction schema could result in overbooking the flight.
Concurrency control prevents the two competing transactions from accessing the same object in a manner which results in anomalies.
Heretofore, two well-known methods of concurrency control, in this field, have included pessimistic concurrency control and optimistic concurrency control. Pessimistic concurrency control is usually associated with locking mechanisms. Optimistic concurrency control, on the other hand, is usually associated with timestamps. At commit time, when the results of a transaction are committed to the database, if the timestamp, which would be the most recent modification time, of any of the objects relied upon by the transaction have been changed, the transaction must have used obsolete data, and is therefore aborted.
Whereas pessimistic concurrency control is preferable in systems with many conflicts, optimistic concurrency control is preferable in systems with few conflicts. It is faster to check timestamps than to check for conflict locks in a lock table. However, if there are many conflicts, many transactions will abort because of their dependence on data which became obsolete during the execution of the transaction.
Because many data base systems have some transactions which rarely cause conflicts and some transactions which frequently cause conflicts, it would be desirable to have a system with combined concurrency control modes, so that some transactions operate optimistically and others operate pessimistically.
A third form of concurrency control is a hybrid concurrency control protocol in which each transaction behaves partially like an optimistic transaction and partially like a pessimistic transaction. Each transaction maintains its own view of the database, by keeping an intentions list, which contains the transaction's sequence of operations. Each record in the intentions list describes the operation, its arguments and its results. The committed state is the intentions lists for committed transactions arranged in timestamp order. Finally, the database contains a set of locks for each active object.
When invoking an operation, the private view of a transaction is first computed from the transaction's intentions list and the committed state of the database. The operation, its arguments and result, are used to check for lock conflict. If a conflict exists, the transaction will wait and retry the operation at a later time.
At commit time, the intentions list of the transaction is incorporated into the committed state of the database and all associated locks held by the transaction are released.
Another form of hybrid concurrency control placed pessimistic features on optimistic transactions, so that transactions can access an object optimistically until it requests a lock on the object. Doing so enables other transactions to access the object and to commit new values of the object until the first transaction acquires a lock on the object. At that point, if the object has been modified by other transactions, the transaction can be aborted. Thus, under that protocol, transactions are neither optimistic nor pessimistic, rather they access some objects pessimistically and other objects optimistically.
In another system, optimistic transactions may be blocked due to conflict with pessimistic transactions. If an optimistic transaction attempts to access an object to which a pessimistic transaction holds a lock, the optimistic transaction goes into a wait state until the pessimistic transaction releases the lock. Thus, in such a system, optimistic transactions lose their optimistic nature when encountering a lock.
Therefore, it would be desirable to have a system in which optimistic and pessimistic transactions can coexist and retain the characteristics associated with their respective transaction types.
As seen above, some of the problems faced have been to enable pessimistic transactions to wait for locks on objects to which they need access, while allowing optimistic transactions to forge ahead without waiting for locks to release, and provide a means by which optimistic and pessimistic transactions can communicate to each other about each other's respective activities on shared objects so that serializability of the transactions can be assured. Accordingly, improvements which overcome any or all of the problems are presently desirable.